home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 2 / Atari Mega Archive CD - Volume 2.iso / minix / up1510b.tgz / up1510b / src / commands / tsort.c < prev    next >
C/C++ Source or Header  |  1990-07-23  |  8KB  |  344 lines
  1. /*
  2. ** topo - perform a topological sort of the output of lorder.
  3. **
  4. ** Usage : topo [infile] [outfile]
  5. **
  6. ** Author: Kent Williams (williams@umaxc.weeg.uiowa.edu)
  7. */
  8.  
  9. #include <stdio.h>
  10. #include <ctype.h>
  11.  
  12. /*
  13. ** for the benefit of the zortech runtime
  14. */
  15. int _okbigbuf = 0;
  16.  
  17. extern char *malloc();
  18. extern char *gets();
  19.  
  20. typedef struct __v {
  21.     struct __v *next;   /* link list node                   */
  22.     int indegree,       /* number of edges into this vertex */
  23.         visited,        /* depth-first search visited flag  */
  24.         on_the_path,    /* used to find cycles              */
  25.         has_a_cycle;    /* true if a cycle at this vertex   */
  26.     struct __e *out;    /* outgoing edges from this vertex  */
  27.     char key[1];        /* name of this vertex              */
  28. } vertex;
  29.  
  30. typedef struct __e {
  31.     struct __e *next;   /* link list node                   */
  32.     vertex *v;          /* vertex to which this edge goes   */
  33. } edge;
  34.  
  35. /*
  36. ** xmalloc -- standard do or die malloc front end.
  37. */
  38. void *
  39. xmalloc(siz)
  40. unsigned siz;
  41. {
  42.     void *rval = (void *)malloc(siz);
  43.     if(rval == NULL) {
  44.         fputs("Out of memory.\n",stderr);
  45.         exit(1);
  46.     }
  47.     return(rval);
  48. }
  49.  
  50. /*
  51. ** edge allocater.
  52. */
  53. edge *
  54. new_edge(v)
  55. vertex *v;
  56. {
  57.     edge *rval;
  58.     rval = (edge *)xmalloc(sizeof(edge));
  59.     rval->v = v; return rval;
  60. }
  61.  
  62. /*
  63. ** copyupto - copy until you see the stop character.
  64. */
  65. char *
  66. copyupto(name,buf,stop)
  67. char *name,*buf,stop;
  68. {
  69.     while(*buf != '\0' && *buf != stop)
  70.         *name++ = *buf++;
  71.     *name = '\0';
  72.     while(*buf != '\0' && isspace(*buf))
  73.         buf++;
  74.     return buf;
  75. }
  76.  
  77. /*
  78. ** find out if the vertex child is a child of the vertex parent.
  79. */
  80. int
  81. child_of(parent,child)
  82. vertex *parent,*child;
  83. {
  84.     edge *e;
  85.     for(e = parent->out; e != NULL && e->v != child; e = e->next)
  86.         ;
  87.     return e == NULL ? 0 : 1;
  88. }
  89.  
  90. /*
  91. ** the vertex set.
  92. **
  93. ** add_v adds a vertex to the set if it's not already there.
  94. */
  95. vertex *vset = NULL;
  96.  
  97. vertex *
  98. add_v(s)
  99. char *s;
  100. {
  101.     vertex *v,*last;
  102.     /*
  103.     ** go looking for this key in the vertex set.
  104.     */
  105.     for(last = v = vset; v != NULL && strcmp(v->key,s) != 0;
  106.         last = v, v = v->next)
  107.         ;
  108.     if(v != NULL) {
  109.         /*
  110.         ** use the move-to-front heuristic to keep this from being
  111.         ** an O(N^2) algorithm.
  112.         */
  113.         if(last != vset) {
  114.             last->next = v->next;
  115.             v->next = vset;
  116.             vset = v;
  117.         }
  118.         return v;
  119.     }
  120.  
  121.     v = (vertex *)xmalloc(sizeof(vertex)+strlen(s));
  122.  
  123.     v->out = NULL;
  124.     strcpy(v->key,s);
  125.     v->indegree =
  126.     v->on_the_path =
  127.     v->has_a_cycle =
  128.     v->visited = 0;
  129.     v->next = vset;
  130.     vset = v;
  131.     return v;
  132. }
  133.  
  134. /*
  135. ** readin -- read in the dependency pairs.
  136. */
  137. void
  138. readin()
  139. {
  140.     static char buf[128];
  141.     static char name[64];
  142.     char *bp;
  143.     vertex *child,*parent;
  144.     edge *e;
  145.     while(gets(buf) != NULL) {
  146.         bp = copyupto(name,buf,' ');
  147.         child = add_v(name);
  148.         parent = add_v(bp);
  149.         if(child != parent && !child_of(parent,child)) {
  150.             e = new_edge(child);
  151.             e->next = parent->out;
  152.             parent->out = e;
  153.             child->indegree++;
  154.         }
  155.     }
  156. }
  157.  
  158. /*
  159. ** the topological sort produces names of modules in reverse of
  160. ** the order we want them in, so use a stack to hold the names
  161. ** until we get them all, then pop them off to print them.
  162. */
  163. struct name { struct name *next; char *s; }
  164. *namelist = NULL;
  165.  
  166. void
  167. pushname(s)
  168. char *s;
  169. {
  170.     struct name *x = (struct name *)xmalloc(sizeof(struct name));
  171.     x->s = s;
  172.     x->next = namelist;
  173.     namelist = x;
  174. }
  175.  
  176. char *
  177. popname() {
  178.     char *rval;
  179.     struct name *tmp;
  180.     if(namelist == NULL)
  181.         return NULL;
  182.     tmp = namelist;
  183.     rval = namelist->s;
  184.     namelist = namelist->next;
  185.     free(tmp);
  186.     return rval;
  187. }
  188.  
  189. /*
  190. ** topo - do a topological sort of the dependency graph.
  191. */
  192. topo() {
  193.     vertex *x;
  194.     edge *e;
  195.     vertex *outq = NULL,*tmp;
  196. #define insq(x) ((x->next = outq),(outq = x))
  197. #define deq() ((tmp = outq),(outq = outq->next),tmp)
  198.  
  199.     /*
  200.     ** find all vertices that don't depend on any other vertices
  201.     ** Since it break the next links to insert x into the queue,
  202.     ** x->next is saved before insq, to resume the list traversal.
  203.     */
  204.     for(x = vset; x != NULL; x = x->next)
  205.         if(x->indegree == 0) {
  206.             insq(x);
  207.             pushname(x->key);       
  208.         }
  209.  
  210.     /*
  211.     ** for each vertex V with indegree of zero,
  212.     **     for each edge E from vertex V
  213.     **        subtract one from the indegree of the vertex V'
  214.     **        pointed to by E.  If V' now has an indegree of zero,
  215.     **        add it to the set of vertices with indegree zero, and
  216.     **        push its name on the output stack.
  217.     */
  218.     while(outq != NULL) {
  219.         x = deq();
  220.         e = x->out;
  221.         while(e != NULL) {
  222.             if(--(e->v->indegree) == 0) {
  223.                 insq(e->v);
  224.                 pushname(e->v->key);
  225.             }
  226.             e = e->next;
  227.         }
  228.     }
  229.     
  230.     /*
  231.     ** print the vertex names in opposite of the order they were
  232.     ** encountered.
  233.     */
  234.     while(namelist != NULL)
  235.         puts(popname());
  236. }
  237.  
  238. /*
  239. ** print_cycle --
  240. ** A cycle has been detected between parent and child.
  241. ** Start with the child, and look at each of its edges for
  242. ** the parent.
  243. **
  244. ** We know a vertex is on the path from the child to the parent
  245. ** because the depth-first search sets on_the_path true for each
  246. ** vertex it visits.
  247. */
  248. void
  249. print_cycle(parent,child)
  250. vertex *parent, *child;
  251. {
  252.     char *s;
  253.     vertex *x;
  254.     edge *e;
  255.     for(x = child; x != parent; ) {
  256.         pushname(x->key);
  257.         for(e = x->out; e != NULL; e = e->next) {
  258.             /*
  259.             ** stop looking for the path at the first node found
  260.             ** that's on the path.  Watch out for cycles already
  261.             ** detected, because if you follow an edge into a cycle,
  262.             ** you're stuck in an infinite loop!
  263.             */
  264.             if(e->v->on_the_path && !e->v->has_a_cycle) {
  265.                 x = e->v;
  266.                 break;
  267.             }
  268.         }
  269.     }
  270.     /*
  271.     ** print the name of the parent, and then names of each of the
  272.     ** vertices on the path from the child to the parent.
  273.     */
  274.     fprintf(stderr,"%s\n",x->key);
  275.     while((s = popname()) != NULL)
  276.         fprintf(stderr,"%s\n",s);
  277. }
  278.  
  279. /*
  280. ** depth first search for cycles in the dependency graph.
  281. ** See "Introduction to Algorithms" by Udi Manber Addison-Wesley 1989
  282. */
  283. void
  284. dfs(v)
  285. vertex *v;
  286. {
  287.     edge *e;
  288.  
  289.     if(v->visited)      /* If you've been here before, don't go again! */
  290.         return;
  291.     v->visited++;
  292.     v->on_the_path++;   /* this node is on the path from the root. */
  293.  
  294.     /*
  295.     ** depth-first search all outgoing edges.
  296.     */
  297.     for(e = v->out; e != NULL; e = e->next) {
  298.         if(!e->v->visited)
  299.             dfs(e->v);
  300.         if(e->v->on_the_path) {
  301.             fprintf(stderr,"cycle found between %s and %s\n",
  302.                 v->key,e->v->key);
  303.             print_cycle(v,e->v);
  304.             v->has_a_cycle++;
  305.         }
  306.     }
  307.     v->on_the_path = 0;
  308. }
  309.  
  310. /*
  311. ** check cycles starts the recursive depth-first search from
  312. ** each vertex in vset.
  313. */
  314. void
  315. check_cycles()
  316. {
  317.     vertex *v;
  318.     struct _vpair *vp;
  319.     for(v = vset; v != NULL; v = v->next)
  320.         dfs(v);
  321. }
  322.  
  323. /*
  324. ** main program.
  325. */
  326. int
  327. main(argc,argv)
  328. int argc;
  329. char **argv;
  330. {
  331.     if(argc > 1 && freopen(argv[1],"r",stdin) == NULL) {
  332.         perror(argv[1]);
  333.         exit(0);
  334.     }
  335.     if(argc > 2 && freopen(argv[2],"w",stdout) == NULL) {
  336.         perror(argv[2]);
  337.         exit(0);
  338.     }
  339.     readin();
  340.     check_cycles();
  341.     topo();
  342. }
  343.  
  344.